1. Field
Embodiments of the invention relate to the field of network processing; and more specifically, to secure fast table lookups for protocols with bidirectional identifiers.
2. Background
Network elements (e.g., routers, switches, etc.) spend a large percentage of their packet processing time performing lookups. For example, network elements commonly lookup one or more identifiers in a given packet to identify corresponding data structures which include data necessary for further processing of the packet.
A class of network protocols exist which exchange locally selected identifiers (which have local significance) as part of a connection establishment sequence. The locally selected identifiers are typically chosen as monotonically increasing numbers or randomly selected numbers. These locally selected identifiers are typically sent in the headers of subsequent packets between the network elements. When a network element selects an identifier for a connection, it inserts the connection data into a table (e.g., a hash table, a balanced binary tree, etc.) using the corresponding local identifier as a key. When the network element receives a data packet, it extracts the local identifier from the packet and uses it as a lookup key to retrieve the connection data from the table.
For example, in the Layer Two Tunneling Protocol version 3 (L2TPv3), defined in request for comments (RFC) 3931, March 2005, the LAC (L2TP Access Concentrator) and the LNS (L2TP Network Server) exchange locally selected identifiers (session identifiers) during each connection establishment sequence. The session data for each session is inserted into a session data structure using the session identifier as a key. Each data packet transmitted between the LAC and LNS includes a session identifier which is used as a lookup key to the session data structure. The information in the session data structure is necessary for correctly processing the packet.
Current lookup mechanisms for identifying corresponding data structures from identifiers in packets include using hash tables or binary trees. Binary trees provide good scalability and consume a predictable amount of memory (e.g., an average of O(log2 N) (big O notation) number of memory access are required to locate the corresponding connection data). Hash tables can provide predictable fast lookup (e.g., O(N/B)), but the memory wasted for unused hash table buckets can be expensive for large data sets and hash tables can require large extents of contiguous memory to be traded off to achieve good performance.
The lookup time using either a binary tree lookup mechanism or a hash table lookup mechanism is not constant. That is, the lookup time varies from element to element even in the same binary tree or hash table. Additionally, the lookup time using a binary tree or a hash table lookup mechanism typically increases as the number of connections increases.